Parallel and Distributed Data Management.
Abstract. Knowledge discovery tools and techniques are used in an increasing number of scientific and commercial areas for the analysis of large data sets. When large data repositories are coupled with geographic distribution of data, users and systems, it is necessary to combine different technologies for implementing high-performance distributed knowledge discovery systems. On the other hand, computational grid is emerging as a very promising infrastructure for high-performance distributed computing. In this paper we introduce a software architecture for parallel and distributed knowledge discovery (PDKD) systems that is built on top of computational grid services that provide dependable, consistent, and pervasive access to high-end computational resources. The proposed architecture uses the grid services and defines a set of additional layers to implement the services of distributed knowledge discovery process on grid-connected sequential or parallel computers. 1
T%2DWarehouse Visual OLAP analysis on trajectory data.

T%2DWarehouse Visual OLAP analysis on trajectory data.

Towards a task%2Dbased search and recommender systems.

A generative pattern model for mining binary datasets.

Mining%40home toward a public%2Dresource computing framework for distributed data mining.

Mining Top%2DK Patterns from Binary Datasets in Presence of Noise.

Mining%40home toward a public%2Dresource computing framework for distributed data mining.

Mining Query Logs.
We propose a new method to rank a special category of time-sensitive queries that are year qualified. The method adjusts the retrieval scores of a base ranking function according to time-stamps of web documents so that the freshest documents are ranked higher. Our method, which is based on feedback control theory, uses ranking errors to adjust the search engine behavior. For this purpose, we use a simple but effective method to extract year qualified queries by mining query logs and a time-stamp recognition method that considers titles and urls of web documents. Our method was tested on a commercial search engine. The experiments show that our approach can significantly improve relevance ranking for year qualified queries even if all the existing methods for comparison failed. 1
Caching content%2Dbased queries for robust and efficient image retrieval.

Challenges in designing an interest%2Dbased distributed aggregation of users in P2P systems.

Frequent spatio%2Dtemporal patterns in trajectory data warehouses.

Caching Algorithms for Similarity Search.

A constraint%2Dbased querying system for exploratory pattern discovery.

Multi%2Dset DHT for Range Queries on Dynamic Data for Grid Information Service.

%28Query%29 History Teaches Everything%2C Including the Future.

A metric cache for similarity search.
Similarity search in metric spaces is a general paradigm that can be used in several application fields. It can also be effectively exploited in content-based image retrieval systems, which are shifting their target towards the Web-scale dimension. In this context, an important issue becomes the design of scalable solutions, which combine parallel and distributed architectures with caching at several levels. To this end, we investigate the design of a similarity cache that works in metric spaces. It is able to answer with exact and approximate results: even when an exact match is not present in cache, our cache may return an approximate result set with quality guarantees. By conducting tests on a collection of one million high-quality digital photos, we show that the proposed caching techniques can have a significant impact on performance, like caching on text queries has been proved effective for traditional Web search engines.
Processing complex similarity queries in peer%2Dto%2Dpeer networks.

Trajectory Data Warehouses Storing and Aggregating Frequent ST Patterns.

A Scalable Distributed Data Structure for Multi%2DFeature Similarity Search.

Spatio%2Dtemporal Aggregations in Trajectory Data Warehouses.

Spatio%2Dtemporal Aggregations in Trajectory Data Warehouses.

Approximate Aggregations in Trajectory Data Warehouses.

Parallel Mining of Frequent Closed Patterns Harnessing Modern Computer Architectures.

Mining query logs to optimize index partitioning in parallel web search engines.

Towards Response Time Estimation in Web Services.

Mining query logs to optimize index partitioning in parallel web search engines.

Nine months in the life of EGEE a look from the South.
South
Client Side Estimation of a Remote Service Execution.
Abstract — many use cases, concerning the monitoring and controlling of real physical instruments, demand deep interaction between users and services that virtualize the access to such instruments/devices. In addition, in order to realize high interoperable solutions, SOA-based Web/Grid Service technologies must be adopted. When the access to one of these services is performed via internet using a Web Service call, the remote invocation time becomes critical in order to understand if an instrument can be controlled properly, or the delays introduced by the wire and the serialization/deserialization process are unacceptable. This paper thus presents methodologies and algorithms, based on a 2 k factorial analysis and a Gaussian Majorization of previous service execution times, which enables the estimation of a generic remote method execution time. Furthermore it suggests three different software architectures, where the developed algorithms and methodology could be integrated in order to automatically profile the end-toend service. It is worth noting that our proposals are validated using suitable benchmarks and extensive tests coming out from a real (not simulated) environment. In addition, the outcome of this paper have been used in the realization of a service for remote control, monitor, and manage of a pool of instruments/devices.
Trajectory Data Warehouses Design Issues and Use Cases.

The many faces of the integration of instruments and the grid.
many faces of the integration of instruments and
Approximate mining of frequent patterns on streams.
Approximate mining of frequent patterns on
Peer%2Dto%2Dpeer systems for discovering resources in a dynamic grid.

Instrument Element A New Grid component that Enables the Control of Remote Instrumentation.


A P2P Resource Discovery System Based on a Forest of Trees.
The convergence of the Grid and Peer-to-Peer (P2P) worlds has led to many solutions that try to efficiently solve the problem of resource discovery on Grids. Some of these solutions are extensions of P2P DHT-based networks. We believe that these systems are not flexible enough in the case the data present in the network is very dynamic, i.e. the data values change very frequently over time. This a very common case for some kind of data in typical Grid systems, like CPU loads, queue occupation, etc. In this paper we present a variation of a previous work based on a tree-shaped P2P overlay network. The system uses Routing Indexes to efficiently route queries and update messages in the presence of highly variable data. The new system is based on a twolevel hierarchical network topology, where tree topologies must be only maintained at the lower level of the hierarchy. The main aim of this new organization is to achieve a simpler maintenance of the overall P2P graph topology. This is reached at the cost of some imprecision in the routing indexes built at the upper level of the graph hierarchy. 

Improving the performance of XML based technologies by caching and reusing information.
the performance of XML based technologies by caching and reusing information
On Interactive Pattern Mining from Relational Databases.
Clustering is an important tool for data mining, since it can  identify major patterns or trends without any supervision (labeled data).
Tree Vector Indexes Efficient Range Queries for Dynamic Content on Peer%2Dto%2DPeer Networks.
Locating data on peer-to-peer networks is a complex issue addressed by many P2P protocols. Most of the research in this area only considers static content, that is, it is often assumed that data in P2P systems do not vary over time. In this paper we describe a data location strategy for dynamic content on P2P networks. Data location exploits a distributed index based on bit vectors: this index is used to route queries towards areas of the system where matches can be found. The bit vectors can be efficiently updated when data is modified. Simulation results show that the proposed algorithms for queries and updates propagation have good performances, also on large networks, even if content exhibits a high degree of variability.
A privacy preserving web recommender system.

Mining frequent closed itemsets out%2Dof%2Dcore.

On Interactive Pattern Mining from Relational Databases.
Clustering is an important tool for data mining, since it can  identify major patterns or trends without any supervision (labeled data).
Boosting the performance of Web search engines Caching and prefetching query results by exploiting historical usage data.
This article discusses efficiency and effectiveness issues in caching the results of queries submitted to a Web search engine (WSE). We propose SDC (Static Dynamic Cache), a new caching strategy aimed to efficiently exploit the temporal and spatial locality present in the stream of processed queries. SDC extracts from historical usage data the results of the most frequently submitted queries and stores them in a static, read-only portion of the cache. The remaining entries of the cache are dynamically managed according to a given replacement policy and are used for those queries that cannot be satisfied by the static portion. Moreover, we improve the hit ratio of SDC by using an adaptive prefetching strategy, which anticipates future requests by introducing a limited overhead over the back-end WSE. We experimentally demonstrate the superiority of SDC over purely static and dynamic policies by measuring the hit ratio achieved on three large query logs by varying the cache parameters and the replacement policy used for managing the dynamic part of the cache. Finally, we deploy and measure the throughput achieved by a concurrent version of our caching system. Our tests show how the SDC cache can be efficiently exploited by many threads
Toward a search architecture for software components.
The Grid and its related technologies enable large-scale sharing of resources of various types. We envision that in the near future applications will be completely built in a bottom-up fashion using software components deployed on various locations and interconnected to form a workflow graph. In this paper, we make some proposals on the design of a component search service, enabling users to locate the components they need to deploy an application. Copyright c ○ 2005 John Wiley &amp; Sons, Ltd. KEY WORDS: Grid computing; workflows; component rank; component search; PageRank 1.
Fast and Memory Efficient Mining of Frequent Closed Itemsets.
Abstract — This paper presents a new scalable algorithm for discovering closed frequent itemsets, a lossless and condensed representation of all the frequent itemsets that can be mined from a transactional database. Our algorithm exploits a divide-and-conquer approach and a bitwise vertical representation of the database, and adopts a particular visit and partitioning strategy of the search space based on an original theoretical framework, which formalizes the problem of closed itemsets mining in detail. The algorithm adopts several optimizations aimed to save both space and time in computing itemset closures and their supports. In particular, since one of the main problems raising up in this type of algorithms is the multiple generation of the same closed itemset, we propose a new effective and memory-efficient pruning technique, which, unlike other previous proposals, does not require the whole set of closed patterns mined so far to be kept in the main memory. This technique also permits each visited partition of the search space to be mined independently in any order and thus also in parallel. The tests conducted on many publicly available datasets show that our algorithm is scalable and outperforms other state-ofthe-art algorithms like CLOSET+ and FP-CLOSE, in some cases by more than one order of magnitude. More importantly, the performance improvements become more and more significant as the support threshold is decreased.
3%2DDimensional Hydrodynamic Interaction of a Supernova Remnant Shock with an Isolated Cloud.

Resource Discovery in a Dynamic Grid Environment.
Resource discovery in a Grid environment is a critical problem, as a typical Grid system includes a very large number of resources, which must be readily identified and accessed to run applications. Traditional Grid discovery algorithms perform poorly, as they do not scale, nor allow Grid-enabled applications to transparently query the whole set of Grid resources. Peer-to-Peer (P2P) has been argued as a suitable distributed paradigm that not only overcomes the issues of scalability of such discovery systems, but also better supports the discovery of resources in a context of dynamicity of resources and associated information. In this paper we propose a P2P system for indexing and discovering Grid resources. We assume that Grid resources are characterized by a set of attributes, and our system can be queried for resources satisfying arbitrary range conditions on these attributes. Note that traditional P2P searching techniques can not be directly applied in this case, since they work well mostly for static content and exact queries. Simulation results show that the system provides an adequate degree of scalability. 1.
Distributed approximate mining of frequent patterns.


Preface Selected Papers from the EUROPVM%2FMPI 2003 Conference


DCI Closed A Fast and Memory Efficient Algorithm to Mine Frequent Closed Itemsets.
One of the main problems raising up in the frequent closed itemsets mining problem is the duplicate detection. In this paper we propose a general technique for promptly detecting and discarding duplicate closed itemsets, without the need of keeping in the main memory the whole set of closed patterns. Our approach can be exploited with substantial performance benefits by any algorithm that adopts a vertical representation of the dataset. We implemented our technique within a new depth-first closed itemsets mining algorithm. The experimental evaluation demonstrates that our algorithm outperforms other state of the art algorithms like CLOSET+ and FPCLOSE. 1.
WebDocs a real%2Dlife huge transactional dataset.

kDCI on using direct count up to the third iteration.

WINGS A Parallel Indexer for Web Contents.

Statistical properties of transactional databases.
Most of the complexity of common data mining tasks is due to the unknown amount of information contained in the data being mined. The more patterns and correlations are contained in such data, the more resources are needed to extract them. This is confirmed by the fact that in general there is not a single best algorithm for a given data mining task on any possible kind of input dataset. Rather, in order to achieve good performances, strategies and optimizations have to be adopted according to the dataset specific characteristics. For example one typical distinction in transactional databases is between sparse and dense datasets. In this paper we consider Frequent Set Counting as a case study for data mining algorithms. We propose a statistical analysis of the properties of transactional datasets that allows for a characterization of the dataset complexity. We show how such characterization can be used in many fields, from performance prediction to optimization. 1.
A new algorithm for gap constrained sequence mining.

Assigning document identifiers to enhance compressibility of Web Search Engines indexes.
Granting efficient accesses to the index is a key issue for the performances of Web Search Engines (WSE). In order to enhance memory utilization and favor fast query resolution, WSEs  use Inverted File (IF) indexes where the posting lists are stored as sequences of d gaps (i.e. differences among successive document identifiers) compressed using variable length encoding methods. This paper describes the use of a lightweight clustering algorithm aimed at assigning the identifiers to documents in a way that minimizes the average values of d gaps. The simulations performed on a real dataset, i.e. the Google contest collection, show that our approach allows to obtain an IF index which is, depending on the d gap encoding chosen, up to 23% smaller than the one built over randomly assigned document identifiers. Moreover, we will show, both analytically and empirically, that the complexity of our algorithm is linear in space and time.
Assigning Document Identifiers to Enhance Compressibility of Fulltext Indices.
F. Silvestri    , R. Perego    , S. Orlando    Istituto ISTI, Consiglio Nazionale delle Ricerche (CNR), Pisa, Italy    Dipartimento di Informatica, Universit a di Venezia, Mestre, Italy  Abstract. Index compression has been a major issue in the field of Information  Retrieval Systems. In particular, due to the impressive figures involved with Web  Search Engines (WSEs) the compression of the index is not an option anymore  but it has become a must. The most important index compression methods are  designed to work for Inverted File (IF) indexes. These methods are based on the  assumption that the posting lists are stored as sequences of d gaps (i.e. differences  among successive document identifiers). The compression is thus carried out by  using variable length encoding methods which represents smaller number using  a smaller number of bits. In this paper, instead of focusing on finding a novel  encoding method, we propose an algorithm which allows the assignment of identifiers  to documents in a way that minimizes the average values of d gaps. The  simulations performed on a real dataset, i.e. the Google contest collection, show  that our approach allows to obtain an IF index which is, depending on the d gap  encoding chosen, up to 23% smaller than the one built over randomly assigned  document identifiers. Moreover, we will show, both analytically and empirically,  that the complexity of our algorithm is linear in space and time.
Assigning identifiers to documents to enhance the clustering property of fulltext indexes.
Web Search Engines provide a large-scale text document retrieval service by processing huge Inverted File indexes. Inverted File indexes allow fast query resolution and good memory utilization since their d-gaps representation can be effectively and efficiently compressed by using variable length encoding methods. This paper proposes and evaluates some algorithms aimed to find an assignment of the document identifiers which minimizes the average values of d-gaps, thus enhancing the effectiveness of traditional compression methods. We ran several tests over the Google contest collection in order to validate the techniques proposed. The experiments demonstrated the scalability and effectiveness of our algorithms. Using the proposed algorithms, we were able to sensibly improve (up to 20.81%) the compression ratios of several encoding schemes.
A Search Architecture for Grid Software Components.
this paper, we are going to discuss the challenges we have to face in designing a search service for locating software components on the Grid. Indeed, the specifications of our search engine rely heavily on the concept of Ecosystem of Components. Basically it consists in an extension of the marketplace concept to the Grid. The ecosystem, in fact, provides applications a virtual environment where they can live (i.e. are executed), and find other components to which they can refer (i.e. cooperate) to build larger (and more complex) systems
Design of a Parallel and Distributed Web Search Engine
This paper describes the architecture of MOSE (My Own Search Engine), a scalable parallel and distributed engine for searching the web. MOSE was specifically designed to efficiently exploit affordable parallel architectures, such as clusters of  workstations. Its modular and scalable architecture can be easily adjusted to fulfill the bandwidth requirements of the application at hand. Both task-parallel  and data-parallel approaches are exploited within MOSE in order to increase  the throughput and efficiently use communication, storing and computational resources. We used
Recent Advances in Parallel Virtual Machine and Message Passing Interface

kDCI a Multi%2DStrategy Algorithm for Mining Frequent Sets.
09:00 Welcome, introduction, results of the global experiments 10:30 Coffee break 11:00 Panel Session I (session chair: tba) &#034;A fast APRIORI implementation&#034;, by Ferenc Bodon &#034;Efficient Implementations of Apriori and Eclat&#034;, by Christian Borgelt
AssistConf a Grid configuration tool for the ASSIST parallel programming environment.
This paper presents AssistConf, a graphical user interface designed to configure an ASSIST program and to run it on a Grid platform. ASSIST (A Software development System based upon Integrated Skeleton Technology) is a new programming environment for the development of parallel and distributed high-performance applications. The main goals of ASSIST are allowing high-level programmability and software productivity for complex multidisciplinary applications, and performance portability across different platforms, including homogenous parallel machines and cluster/Beowulf systems, heterogeneous clusters, and computational Grids. AssistConf is used to configure the ASSIST program and establish a mapping between the program modules and the most suitable machines in the Grid candidate to execute them. It simplifies the creation of the XML ASSIST configuration file, giving users the machines to be used for execution. Finally, the configuration  program over the Grid.
A Hybrid Strategy for Caching Web Search Engine Results.
This work discusses the design and implementation of an efficient caching system aimed to exploit the locality present in the queries submitted to a Web Search Engine (WSE). We enhance previous proposals in several directions. First we propose the adoption of a hybrid strategy for caching, and then we experimentally demonstrate the superiority of our hybrid strategy. Further we show how to take advantage of the spatial locality present in WSE query logs by exploiting a sort of adaptive prefetching strategy.
Scheduling High Performance Data Mining Tasks on a Data Grid Environment.
Increasingly the datasets used for data mining are becoming huge and physically  distributed. Since the distributed knowledge discovery process is both data and computational  intensive, the Grid is a natural platform for deploying a high performance data mining  service. The focus of this paper is on the core services of such a Grid infrastructure. In particular  we concentrate our attention on the design and implementation of specialized Resource  Allocation and Execution Management services aware of data source locations and resource  needs of data mining tasks. Allocation and scheduling decisions are taken on the basis of  performance cost metrics and models that exploit knowledge about previous executions, and  use sampling to acquire estimate about execution behavior.
Adaptive and Resource%2DAware Mining of Frequent Sets.
The performance of an algorithm that mines frequent sets from transactional databases may severely  depend on the specific features of the data being analyzed. Moreover, some architectural characteristics  of the computational platform used -- e.g. the available main memory -- can dramatically change the  runtime behaviors of the algorithm. In this paper we present DCI (Direct Count &amp; Intersect), an e#cient  data mining algorithm for discovering frequent sets from large databases, which e#ectively addresses the  issues mentioned above. DCI adopts a classical level-wise approach based on candidate generation to  extract frequent sets, but uses a hybrid method to determine candidate supports. The most innovative  contribution of DCI relies on the multiple heuristics strategies employed, which permits DCI to adapt its  behavior not only to the features of the specific computing platform, but also to the features of the dataset  being mined, so that it results e#ective in mining both short and long patterns from sparse and dense  datasets. The large amount of tests conducted permit us to state that DCI sensibly outperforms state-ofthe  -art algorithms for both synthetic and real-world datasets. Finally we also discuss the parallelization  strategies adopted in the design of ParDCI, a distributed and multi-threaded implementation of DCI.
An Efficient Parallel and Distributed Algorithm for Counting Frequent Sets.
Due to the huge increase in the number and dimension of  available databases, e#cient solutions for counting frequent sets are nowadays  very important within the Data Mining community. Several sequential  and parallel algorithms were proposed, which in many cases exhibit  excellent scalability. In this paper we present ParDCI, a distributed and  multithreaded algorithm for counting the occurrences of frequent sets  within transactional databases. ParDCI is a parallel version of DCI (Direct  Count &amp; Intersect), a multi-strategy algorithm which is able to adapt its  behavior not only to the features of the specific computing platform (e.g.
Enhancing the Apriori Algorithm for Frequent Set Counting.
In this paper we propose DCP, a new algorithm for solving the Frequent Set Counting problem, which enhances Apriori. Our goal was to optimize the initial iterations of Apriori, i.e. the most time consuming ones when datasets characterized by short or medium length frequent patterns are considered. The main improvements regard the use of an innovative method for storing candidate set of items and counting their support, and the exploitation of effective pruning techniques which significantly reduce the size of the dataset as execution progresses.
Integrating HPF in a Skeleton Based Parallel Language.
Although HPF allows programmers to express data-parallel computations in a portable, high-level way, it is widely accepted that many important parallel applications cannot be efficiently implemented following a pure data-parallel paradigm. For these applications, rather than having a single data-parallel program, it is more profitable to subdivide the whole computation into several data-parallel pieces, where the various pieces run concurrently and co-operate, thus exploiting task parallelism. This paper discusses the integration of HPF with SkIE, a skeleton based coordination language implemented on top of MPI (Message Passing Interface), which permits to describe complex computational parallel structures. We show how HPF can be used inside common forms of parallelism, e.g. pipeline and processor farms, and we present experimental results regarding a sample application.
Implementation Issues in the Design of I%2FO Intensive Data Mining Applications on Clusters of Workstations.
This paper investigates scalable implementations of out-of-core  I/O-intensive Data Mining algorithms on aordable parallel architectures,  such as clusters of workstations. In order to validate our approach,  the K-means algorithm, a well known DM Clustering algorithm,  was used as a test case. 
Integrating task and data parallelism with taskHPF.
Many applications exhibit a large amount of potential parallelism that can be exploited at both data and  task levels. In this paper, we consider applications which can be structured as ensembles of independent  data parallel HPF modules (hereafter HPF tasks). We also assume that HPF tasks interact according to a  static and predictable structure. We describe taskHPF a coordination language in which the user can dene  the HPF tasks with a clean input and output interface, and program the global interaction structure among  tasks in a declarative way. We examine a small example application to discuss the benets of our approach,  and we show how taskHPF programs can be translated into ecient message-passing code.  1 Introduction  Many applications show potential for exploiting both data and task parallelism. Data parallelism is characterized by the application of the same operation to dierent parts of the related data set. In task parallelism, distinct parts of the program proceed ind...
Coordinating HPF Programs to Mix Task and Data Parallelism.
Experience in applicative elds, above all deriving from the development of multidisciplinary parallel applications, seems to suggest a model where an outer coordination level is provided to allow data parallel tasks to run concurrently and to cooperate each other. The inner computational level of this coordination model can easily be expressed with HPF, a high-level data-parallel language. According to this model, we devised COLT HPF , a coordination architectural layer that supports dynamic creation and concurrent execution of HPF tasks, and permits these tasks to cooperate though message passing. This paper proposes the exploitation of COLT HPF by means of a simple skeleton{based coordination language and the associated source-to-source compiler. Dierently from other related proposals, COLT HPF is portable and can exploit commercial, standard-compliant, HPF compilation systems. We used a physics application as a test-case for our approach, and we present the results of several expe...
Mixed data and task parallelism with HPF and PVM.
this paper we present COLT HPF (COordination Layer for Tasks expressed in HPF), a portable coordination /communication layer for HPF tasks. COLT HPF is implemented on top of PVM and provides suitable mechanisms for starting, even at run{time, instances of data-parallel tasks on disjoint groups of (PVM virtual) processors, along with optimized primitives for intertask communication where data to be exchanged may be distributed among the processors according to userspeci ed HPF directives.
COLTHPF%2C a run%2Dtime support for the high%2Dlevel co%2Dordination of HPF tasks.
ions (SDAs), using a syntax similar to that of HPF. Each instance of an SDA encapsulates distributed data and methods, where methods have exclusive access to encapsulated data. Data parallel tasks are thus started by creating instances of specific SDAs, while the inter-task co-operation takes place by means of remote synchronous (or asynchronous) method invocations. Note that SDA instances are started dynamically by a so called coordination  task, so that the run-time that implements inter-task communication has to control passing distributed data structures from one task to another, including any possible remapping that might be needed. The run-time accomplishes this through a handshaking protocol, which exchanges the distribution information about the actual argument (on the caller SDA) and the formal one (on the callee SDA) of a given method. Note that this handshaking protocol is very similar to the COLT HPF protocol to create a channel between two tasks. Finally, even though in th...
SUPPLE An efficient run%2Dtime support for non%2Duniform parallel loops.
To efficient implement parallel loops on distributed--memory multicomputers, data parallel languages generally exploit static data layout and static scheduling of iterations. Unfortunately, when iteration execution costs vary considerably and are unpredictable, some processors may be assigned more work than others. Workload imbalance can be mitigated by cyclically distributing data and associated computations. Though this strategy often solves load balance issues, it may worsen data locality exploitation. This paper presents SUPPLE (SUPort for Parallel Loop Execution), an innovative run-- time support for parallel loops with regular stencil data references and non--uniform iteration costs. SUPPLE relies upon a static block data distribution to exploit locality, and combines static and dynamic policies for scheduling non--uniform iterations. It adopts, as far as possible, a static scheduling policy derived from the owner computes rule, and moves data and iterations among processors only...
Scheduling Data%2DParallel Computations on Heterogeneous and Time%2DShared Environments.
This paper addresses the problem of load balancing data--parallel computations on heterogeneous and time-shared parallel computing environments. Load imbalance in these environments may be introduced by the different capacities of processors populating a computer, or by the sharing of the same computational resources among several users. A evenly partitioned code, which on a homogeneous system runs with a perfect load balance, may perform poorly if the processors have different speeds or loads. To solve this problem for data--parallel computations, we propose a run--time support for parallel loops based upon a hybrid (static + dynamic) scheduling strategy. Our support balances the processor workloads by dynamically migrating computations from slower to faster processors without requiring a priori knowledge of their relative speeds. The results obtained on many experiments conducted on SGI/Cray T3E and IBM SP2 systems show that our hybrid scheduling strategy which first allocates the sa...
A Coordination Layer for Exploiting Task Parallelism with HPF.

An MPI%2Dbased Run%2DTime Support to Coordinate HPF Tasks.
. This paper describes COLT HPF , an MPI--based run--time support for the coordination of concurrent and communicating HPF tasks.  COLT HPF is conceived for use by a compiler of a high-level coordination language to structure a set of data-parallel HPF tasks according to popular forms of task-parallelism. Since it requires only small changes to the run-time support of the HPF compiler used, COLT HPF is easily portable among different compilation systems. The paper outlines design and implementation issues, and reports the results of experiments conducted on an SGI/Cray T3E. 1 Introduction  Due to its simplicity, the data-parallel programming model allows high-level parallel languages such as HPF [9] to be designed, which hide low-level programming details and let programmers to concentrate on the high-level exploitation of data parallelism. The compiler manages data distribution and translates the annotated source program into an SPMD code with explicit interprocessor communications an...
A Comparison of Implementation Strategies for Nonuniform Data%2DParallel Computations.

A Support for Non%2Duniform Parallel Loops and Its Application to a Flame Simulation Code.
. This paper presents SUPPLE (SUPport for Parallel Loop Execution), an innovative run--time support for parallel loops with regular stencil data references and non--uniform iteration costs. SUPPLE relies upon a static block data distribution to exploit locality, and combines static and dynamic policies for scheduling non--uniform iterations. It adopts, as far as possible, a static scheduling policy derived from the owner computes rule, and moves data and iterations among processors only if a load imbalance actually occurs. SUPPLE always tries to overlap communications with useful computations by reordering loop iterations and prefetching remote ones in the case of workload imbalance. The SUPPLE approach has been validated by many experimental results obtained by running a multi-dimensional flame simulation kernel on a 64--node Cray T3D. We have fed the benchmark code with several synthetic input data sets built on the basis of a load imbalance model, and we have compared our results wi...
A Load Balancing Strategy for Iterated Parallel Loop Scheduling.
. An efficient template for the implementation on distributedmemory  multiprocessors of iterated parallel loops, i.e. parallel loops nested  in a sequential loop, is presented. The template is explicitly designed to  smooth unbalanced processor workloads deriving from loops whose iterations  are characterized by highly varying execution times. Experiments  conducted shows performance gains w.r.t. HPF-like language supports.  1 Introduction  The effective exploitation of parallel loops is the key to achieve considerable speedups in many scientific compute-intensive applications. Data parallel languages such as HPF rely on user-provided directives to derive the distribution of data and on the owner computes rule [4] to determine static schedules of parallel loops from the provided data distribution. The choice of the best data distribution  (blocking or cyclic) is currently up to programmers. Note that, for some non--uniform problems, it is impossible to find a good distribution scheme i...
A Template for Non%2DUniform Parallel Loops Based on Dynamic Scheduling and Prefetching Techniques.
In this paper we present an efficient template for the implementation on distributed-memory multiprocessors of non-- uniform parallel loops, i.e. loops whose independent iterations are characterized by highly varying execution times. The template relies upon a static blocking distribution of array data sets to exploit locality, and a hybrid scheduling policy to smooth uneven processor finishing time. It initially adopts a static scheduling technique based on the  owner computes rule. As soon as a workload imbalance is detected, it exploits a dynamic receiver initiated technique to move work towards unloaded processors. Prefetching is used to reduce overheads due to the communications needed to monitor the load, move iterations, and restore the consistency of migrated data. Accurate performance costs of the technique can be derived, thus allowing the template to be used by a compiler to generate well-balanced code for non--uniform parallel loops. Experiments were conducted on a 64-node ...
Exploiting partial replication in unbalanced parallel loop scheduling on multicomputer.
We consider the problem of scheduling parallel loops whose iterations operate on large array data structures and are characterized by highly varying execution times (unbalanced or non-uniform parallel loops). A general parallel loop implementation template for message-passing distributed-memory multiprocessors (multicomputers) is presented. Assuming that it is impossible to statically determine the distribution of the computational load on the data accessed, the template exploits a hybrid scheduling strategy. The data are partially replicated on the processor&#039;s local memories and iterations are statically scheduled until first load imbalances are detected. At this point an effective dynamic scheduling technique is adopted to move iterations among nodes holding the same data. Most of the communications needed to implement dynamic load balancing are overlapped with computations, as a very effective prefetching policy is adopted. The template scales very well, since knowing where data are...
Summarising an experiment in parallel programming language design.

P3 L A structured high%2Dlevel parallel language
This paper presents a parallel programming methodology that ensures easy programming, efficiency, and portability of programs to different machines belonging to the class of the general-purpose, distributed memory, MIMD architectures. The methodology is based on the definition of a new, high-level, explicitly parallel language, called P^3L, and of a set of static tools that automatically adapt the program features for each target architecture. P^3 L does not require programmers to specify process activations, the actual parallelism degree, scheduling, or interprocess communications, i.e. all those features that need to be adjusted to harness each specific target machine. Parallelism is, on the other hand, expressed in a structured and qualitative way, by hierarchical composition of a restricted set of language constructs, corresponding to those forms of parallelism that are frequently encountered in parallel applications, and that can be efficiently implemented. The eff...
Compiling Geometric Paradigms through Local Communications.
This paper presents a compiling technique to generate parallel code with explicit local communications for a mesh-connected distributed memory, MIMD architecture. Our compiling technique works for the geometric paradigm of parallel computation, i.e. a
Efficient Compilation of Structured Parallel Programs for Distributed Memory MIMD Machines.

A Synchronous Model for Static Optimizations of Multicomputer Programs.


Database Analyzer and Predictor %2D An Overview.

Strategies for a Massively Parallel Implementation of Simulated Annealing.

Integrated Tools for Physical Database Design in CODASYL Environment.


Probabilistic Appraoch to Evaluation of Data Manipulation Algorithms in a CODASYL Data Base Environment.

